Điều kiện cần: Giả sử (G) là đồ thị Euler, tức là tồn tại
chu trình Euler (P) trong (G). Khi đó, cứ mỗi lần chu trình (P) đi qua một đỉnh nào đó của (G) thì
bậc của đỉnh đó tăng lên 2.Mặt khác, mỗi cạnh của đồ thị xuất hiện trong (P) đúng 1 lần. Do đó, mỗi đỉnh của đồ thị đều có
bậc chẵn
Hình 6: Xây dựng quy nạp đường điTrong đó v1 là đỉnh kề với v, còn với i ≥ 1, chọn vi+1 là đỉnh kề với vi và vi+1 ≠ vi-1 (có thể chọn như vậy vì
deg(vi) ≥ 2), v0 = v. Do tập đỉnh của (G) là hữu hạn, nên sau một số hữu hạn bước ta phải quay lại 1 đỉnh đã xuất hiện trước đó. Gọi k là số nguyên dương đầu tiên để vk = vi. Khi đó, đường đi vi, vi+1,...., vk-1, vk là một
chu trình đơn cần tìm
- Điều kiện đủ: Quy nạp theo số cạnh của (G). Do (G) liên thông và bậc của mọi đỉnh là chẵn nên mọi đỉnh có bậc không nhỏ hơn 2. Từ đó theo bổ đề nêu trên, (G) phải chứa 1 chu trình đơn (C). Nếu (C) đi qua tất cả các cạnh của (G) thì nó chính là chu trình Euler. Giả sử (C) không đi qua tất cả các cạnh của (G). Khi đó loại bỏ khỏi (G) các cạnh thuộc (C), ta thu được 1 đồ thị mới (H)(không nhất thiết là liên thông). Số cạnh trong (H) nhỏ hơn trong (G) và rõ ràng mỗi đỉnh của (H) vẫn có bậc chẵn.
Theo giả thuyết
quy nạp, trong mỗi thành phần liên thông của (H) đều tìm được
chu trình Euler. Do (G)
liên thông nên mỗi thành phần trong (H) có ít nhất một đỉnh chung với chu trình (C). Vì vậy có thể xây dựng
chu trình Euler trong (G) như sau:
Hình 7: Chu trình Euler trong (G)Bắt đầu từ 1 đỉnh nào đó của chu trình (C), đi theo các cạnh của (C) chừng nào chưa gặp phải đỉnh không cô lập của (H). Nếu gặp phải đỉnh như vậy thì ta đi theo
chu trình Euler của
thành phần liên thông của (H) chứa đỉnh đó. Sau đó lại tiếp tục đi theo cạnh của (C) cho đến khi gặp phải đỉnh không cô lập của (H) thì lại theo
chu trình Euler của
thành phần liên thông tương ứng trong (H),.... Quá trình sẽ kết thúc khi ta trở về đỉnh xuất phát, tức là thu được chu trình đi qua mỗi cạnh của đồ thị đúng 1 lần.
- Hệ quả: Đồ thị liên thông (G) là nửa Euler (mà không là Euler) khi và chỉ khi có đúng 2 đỉnh bậc lẻ trong (G).
- Chứng minh: Nếu (G) là đồ thị nửa Euler thì tồn tại một đường đi Euler trong (G) từ đỉnh u đến đỉnh v. Gọi (G') là đồ thị thu được từ (G) bằng cách thêm vào cạnh (u,v). Khi đó (G') là đồ thị Euler nên mọi đỉnh trong (G') đều có bậc chẵn (kể cả u và v). Vì vậy u và v là 2 đỉnh duy nhất trong (G) có bậc lẻ.
Đảo lại, nếu có đúng 2 đỉnh
bậc lẻ là u và v thì gọi (G') là đồ thị thu được từ (G) bằng cách thêm vào cạnh (u,v). Khi đó mọi đỉnh của (G') đều có
bậc chẵn hay (G') là
đồ thị Euler. Bỏ cạnh (u,v) đã thêm vào ra khỏi
chu trình Euler trong (G') ta có được
đường đi Euler từ u đến v trong (G) hay (G) là
đồ thị nửa Euler.
